class Solution 
{
   
public:
    int findKthLargest(vector<int>& nums, int k) 
    {
        srand(time(nullptr));
        return quicksort(nums,0,nums.size()-1,k);
    
    }
    //在left right找第k大的元素
   int quicksort(vector<int>&nums,int left,int right,int k)
    {
        int key=nums[(rand()%(right-left+1))+left];
        int begin=left-1;
        int end=right+1;
        int index=left;
        while(index<end)
        {
            if(nums[index]==key) index++;
            else if(nums[index]<key) swap(nums[++begin],nums[index++]);
            else swap(nums[--end],nums[index]);
        }
        int a=begin-left+1;
        int b=end-begin-1;
        int c=right-end+1;
        if(c>=k) return quicksort(nums,end,right,k);
        else if(b+c>=k) return key;
        //此时右边都不满足 那就转换成了在左边
        else return quicksort(nums,left,begin,k-c-b);
    }
};